//
// Created by Administrator on 2024/9/3.
//

#include <iostream>
#include "arrUtil.h"

using namespace std;

int part(vector<int> &v,int l, int r)
{
    int value = v[l], le = l;
    for (int i = l+1; i <= r ; ++i)
    {
        if(v[i]<=value)
        {
            ++le;
            swap(v[i],v[le]);
        }
    }
    swap(v[le],v[l]);
    return le;
}


void quickSort(vector<int> &v,int l, int r)
{
    if (l<r)
    {
        int m= part(v,l,r);
        quickSort(v,l,m-1);
        quickSort(v,m+1,r);
    }
}
int main()
{
    vector<int> arr{7, 9, 8, 7, 4, 3, 3, 6};
//    cout<<part(arr,0,8);
    randVector(arr,1000);
    quickSort(arr,0,999);
//    printVector(arr);
    cout<<checkSortVector(arr);
    return 0;
}